The field of digital data compression and in particular digital image compression has attracted a great interest for some time. Recently, compression schemes based on a Discrete Wavelet Transform (DWT) have become increasingly popular because the DWT offers a non-redundant hierarchical decomposition of an image and resultant compression of the image provides favourable rate-distortion statistics.
Typically, the discrete wavelet transform (DWT) of an image is performed using a series of one-dimensional DWTs. A one-dimensional DWT of a signal (ie. an image row) is performed by lowpass and highpass filtering the signal, and decimating each filtered signal by 2. Decimation by 2 means that only every second sample of the filtering processes is calculated and retained. When performing a convolution (filtering) the filter is moved along by two samples at a time, instead of the usual one sample, to effect the decimation by 2. In this way, for a signal of N samples, there are N DWT samples, N/2 lowpass samples, and N/2 highpass samples. Strictly speaking this is a single level one dimensional DWT. However, since only single level one-dimensional DWTs are used in this description, they are referred to simply as a one-dimensional DWT (1D DWT).
FIG. 1 illustrates a typical process for performing a single level two-dimensional DWT of an input image 100. Each column of the image 100 is analysed with a one-dimensional DWT giving output columns whose first half comprise lowpass samples and whose second half comprise highpass samples. A single level one-dimensional DWT of a column is referred to as a column DWT. Such analysis of each column of the input image 100 results in a coded representation 101 having two sub-images labelled Lc and Hc. The columns of Lc are formed of the lowpass filtered (and decimated) columns of the input image 100 and the columns of Hc are formed of the highpass filtered (and decimated) columns of the input image 100. The coded representation 101 may then be considered as an output image, the rows of which are then analysed with a one-dimensional DWT, or row DWT, as also illustrated in FIG. 1. This results in a further coded representation 102 having four sub-images or subbands, labelled LL, HL, LH and HH, where L and H refer to lowpass and highpass respectively, and in the two letter label, the first letter corresponds to the row filter, while the second to the column filter. That is, the HL subband is the result of lowpass filtering the columns (and decimating by 2) and highpass filtering the resulting rows (and decimating by 2). The LL subband is also called the DC or low frequency subband while the HL, LH and HH are called AC or high frequency subbands. Depending on the context, a single level two-dimensional DWT 102 of an image 100 can be referred to as a single level DWT (or even simply DWT) of the image 100.
Each one-dimensional DWT can be inverted. That is, having analysed a one-dimensional signal of N samples into N/2 lowpass and N/2 highpass subband samples, these subband samples, of which there are N in total, can be synthesized with a one-dimensional inverse DWT, into the N samples of the original one-dimensional signal. Thus, the original image can be reconstructed by synthesising the rows then the columns of a single level DWT of an image. This is also illustrated in FIG. 1. Thus a single level (two-dimensional) DWT is invertible. The process of a inverting a DWT is often referred to as synthesis or applying and an inverse DWT, or simply iDWT.
To obtain a two level DWT the LL subband is further analysed with a single level DWT into four subbands, just as the original image was analysed into four subbands. To obtain a three level DWT, the LL subband resulting from the two level DWT is again analysed. Such a process can be perfomed in similar fashion for an arbitrary number of levels. Thus a multi-level DWT or simply DWT of an image can be performed by iterating a single level DWT some finite number of times on subsequent LL subbands, where the first LL subband is the original image (e.g. 100). A multi-level DWT can be inverted by simply inverting each single level DWT.
At each level of a multi-level DWT there are three high frequency subbands, the HL, LH and HH subbands. Therefore, for a more precise notation a level number is included in the labelling of the subbands. Thus the four subbands illustrated in the coded representation 102 of FIG. 1 are more precisely denoted LL1, HL1, LH1 and HH1. Similarly the three high frequency subbands at level 2, resulting from the single level DWT of the LL1 subband, are denoted HL2, LH2 and HH2. Using this subband notation the original image 100 can be labelled as the LL0 subband.
In some image compression methods the subbands resulting from a DWT are tiled into blocks of samples, called code-blocks. For example, each block consists of, say, H rows by H columns. A row of blocks in a subband is formed of H lines of the subband. Typically, each block (code-block) is quantised and entropy coded substantially independently. Thus each block can be entropy decoded (and dequantized) independently. A block essentially becomes a minimum coded unit. The blocks are not necessarily strictly independently encoded. Some small amount of information, such as the most significant bit plane in each block, may be coded together for all blocks in a subband. However, if the time or effort required to encode or decode such information for one block is trivial when compared to encoding or decoding a whole block, then for present purposes it may be considered that the blocks are coded independently. Such image compression methods are referred to herein as block-based DWT image compression methods.
Other compression methods such as JPEG employ a block discrete cosine transform (DCT) to map data into a frequency domain. Typically an image is tiled in the spatial domain into 8×8 blocks of pixels. Each 8×8 block is transformed into a block of 8×8 coefficients, including 1 DC coefficient, and 63 AC coefficients. For baseline JPEG, the coefficients are quantized and coded into one entropy coded segment in the compressed image bit-stream. This segment then represents the original 8×8 block of pixels. Apart from a small coupling of the DC coefficients, there is a 1-1 relationship between the 8×8 blocks in the image domain and entropy coded segments.
For typical compression rates, many of the coefficients are quantized to zero and hence dequantized to zero. At the decoder, each block of 8×8 pixels is reconstructed substantially independently. Firstly the quantized DCT coefficients are decoded from the compressed bit-stream. The DC value is reconstructed from the current difference and the previous blocks DC value. The coefficients are then dequantized and inverse transformed with an inverse DCT. Many inverse (and forward) DCT techniques employ a series of one dimensional DCT's. Firstly all the columns are inverse transformed, and then all the rows. For each column a test may be made if each of the AC coefficients are zero. If so, a faster version of the inverse column DCT can be employed, providing a speed-up for the overall two-dimensional DCT. This technique is employed by the Independent JPEG Group (IJG) code which is widely used in JPEG compression and decompression software. A similar test can also be employed when performing the inverse row DCT's. However, if the row inverse DCT's are employed after the column inverse DCT's the likelihood of all the AC coefficients being zero is significantly less that for the column inverse DCT's. In some cases the overhead required to test each row can result in a slower overall inverse two-dimension DCT, which is contrary to the intended purpose.
The 1-1 mapping between 8×8 blocks of coefficients and 8×8 blocks of pixels facilitate using knowledge of the zero-valued coefficients to accelerate the inverse DCT. If a set of AC coefficients (ie a column) is zero, then it is known that all relevant AC coefficients that can effect this block are zero. That is there is no overlap from adjacent blocks, and AC coefficients in adjacent (or other) blocks have no effect on the pixels resulting from the inverse transform of the current block.
For block-based DWT image compression methods, decompression involves entropy decoding compressed blocks of subband samples, and then an inverse DWT is performed on the resulting subbands. As with the DCT, at typical compression rates (for example 1 bit per pixel), many of the high frequency subband coefficients are quantized to 0. A rough correspondence can be derived between a set of DWT coefficients and a set of the same size of image domain pixels. However, for overlapping filters, such as those employed by the JPEG2000 standard (ISO/IEC 15-1:2000), the image domain pixels actually depend on a greater number of DWT coefficients: namely some of those adjacent to the given set of DWT coefficients. This non 1:1 relationship between subband and image domain blocks means that identifying all corresponding AC subband blocks are zero is not sufficient to determine that the corresponding output block can be generated assuming zero AC subband values.
Further, the inverse DWT is usually performed one-level at a time. There are thus 3 AC coefficients for every DC coefficient, for each level of the inverse DWT. The smaller number of AC coefficients relative to the DC coefficients, and the greater amount of overlapping state means that the IJG approach referred to above to reduce computation (based on zero valued AC coefficients) cannot be simply adopted in an efficient manner to the case of an inverse DWT.